home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Berkeley DB 1.6 / hash / hash_page.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-18  |  23.9 KB  |  1,014 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_page.c    8.1 (Berkeley) 6/6/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * PACKAGE:  hashing
  43.  *
  44.  * DESCRIPTION:
  45.  *    Page manipulation for hashing package.
  46.  *
  47.  * ROUTINES:
  48.  *
  49.  * External
  50.  *    __get_page
  51.  *    __add_ovflpage
  52.  * Internal
  53.  *    overflow_page
  54.  *    open_temp
  55.  */
  56.  
  57. #include <sys/types.h>
  58.  
  59. #include <errno.h>
  60. #include <fcntl.h>
  61. #include <signal.h>
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65. #include <unistd.h>
  66. #ifdef DEBUG
  67. #include <assert.h>
  68. #endif
  69.  
  70. #ifdef macintosh
  71. #include <machine/endian.h>
  72. #include <sys/errno.h>
  73. #endif
  74.  
  75. #include <db.h>
  76. #include "hash.h"
  77. #include "page.h"
  78. #include "extern.h"
  79.  
  80. static u_long    *fetch_bitmap __P((HTAB *, int));
  81. static u_long     first_free __P((u_long));
  82. static int     open_temp __P((HTAB *));
  83. static u_short     overflow_page __P((HTAB *));
  84. static void     putpair __P((char *, const DBT *, const DBT *));
  85. static void     squeeze_key __P((u_short *, const DBT *, const DBT *));
  86. static int     ugly_split
  87.             __P((HTAB *, u_int, BUFHEAD *, BUFHEAD *, int, int));
  88.  
  89. #define    PAGE_INIT(P) { \
  90.     ((u_short *)(P))[0] = 0; \
  91.     ((u_short *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_short); \
  92.     ((u_short *)(P))[2] = hashp->BSIZE; \
  93. }
  94.  
  95. /*
  96.  * This is called AFTER we have verified that there is room on the page for
  97.  * the pair (PAIRFITS has returned true) so we go right ahead and start moving
  98.  * stuff on.
  99.  */
  100. static void
  101. putpair(p, key, val)
  102.     char *p;
  103.     const DBT *key, *val;
  104. {
  105.     register u_short *bp, n, off;
  106.  
  107.     bp = (u_short *)p;
  108.  
  109.     /* Enter the key first. */
  110.     n = bp[0];
  111.  
  112.     off = OFFSET(bp) - key->size;
  113.     memmove(p + off, key->data, key->size);
  114.     bp[++n] = off;
  115.  
  116.     /* Now the data. */
  117.     off -= val->size;
  118.     memmove(p + off, val->data, val->size);
  119.     bp[++n] = off;
  120.  
  121.     /* Adjust page info. */
  122.     bp[0] = n;
  123.     bp[n + 1] = off - ((n + 3) * sizeof(u_short));
  124.     bp[n + 2] = off;
  125. }
  126.  
  127. /*
  128.  * Returns:
  129.  *     0 OK
  130.  *    -1 error
  131.  */
  132. extern int
  133. __delpair(hashp, bufp, ndx)
  134.     HTAB *hashp;
  135.     BUFHEAD *bufp;
  136.     register int ndx;
  137. {
  138.     register u_short *bp, newoff;
  139.     register int n;
  140.     u_short pairlen;
  141.  
  142.     bp = (u_short *)bufp->page;
  143.     n = bp[0];
  144.  
  145.     if (bp[ndx + 1] < REAL_KEY)
  146.         return (__big_delete(hashp, bufp));
  147.     if (ndx != 1)
  148.         newoff = bp[ndx - 1];
  149.     else
  150.         newoff = hashp->BSIZE;
  151.     pairlen = newoff - bp[ndx + 1];
  152.  
  153.     if (ndx != (n - 1)) {
  154.         /* Hard Case -- need to shuffle keys */
  155.         register int i;
  156.         register char *src = bufp->page + (int)OFFSET(bp);
  157.         register char *dst = src + (int)pairlen;
  158.         memmove(dst, src, bp[ndx + 1] - OFFSET(bp));
  159.  
  160.         /* Now adjust the pointers */
  161.         for (i = ndx + 2; i <= n; i += 2) {
  162.             if (bp[i + 1] == OVFLPAGE) {
  163.                 bp[i - 2] = bp[i];
  164.                 bp[i - 1] = bp[i + 1];
  165.             } else {
  166.                 bp[i - 2] = bp[i] + pairlen;
  167.                 bp[i - 1] = bp[i + 1] + pairlen;
  168.             }
  169.         }
  170.     }
  171.     /* Finally adjust the page data */
  172.     bp[n] = OFFSET(bp) + pairlen;
  173.     bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_short);
  174.     bp[0] = n - 2;
  175.     hashp->NKEYS--;
  176.  
  177.     bufp->flags |= BUF_MOD;
  178.     return (0);
  179. }
  180. /*
  181.  * Returns:
  182.  *     0 ==> OK
  183.  *    -1 ==> Error
  184.  */
  185. extern int
  186. __split_page(hashp, obucket, nbucket)
  187.     HTAB *hashp;
  188.     u_int obucket, nbucket;
  189. {
  190.     register BUFHEAD *new_bufp, *old_bufp;
  191.     register u_short *ino;
  192.     register char *np;
  193.     DBT key, val;
  194.     int n, ndx, retval;
  195.     u_short copyto, diff, off, moved;
  196.     char *op;
  197.  
  198.     copyto = (u_short)hashp->BSIZE;
  199.     off = (u_short)hashp->BSIZE;
  200.     old_bufp = __get_buf(hashp, obucket, NULL, 0);
  201.     if (old_bufp == NULL)
  202.         return (-1);
  203.     new_bufp = __get_buf(hashp, nbucket, NULL, 0);
  204.     if (new_bufp == NULL)
  205.         return (-1);
  206.  
  207.     old_bufp->flags |= (BUF_MOD | BUF_PIN);
  208.     new_bufp->flags |= (BUF_MOD | BUF_PIN);
  209.  
  210.     ino = (u_short *)(op = old_bufp->page);
  211.     np = new_bufp->page;
  212.  
  213.     moved = 0;
  214.  
  215.     for (n = 1, ndx = 1; n < ino[0]; n += 2) {
  216.         if (ino[n + 1] < REAL_KEY) {
  217.             retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
  218.                 (int)copyto, (int)moved);
  219.             old_bufp->flags &= ~BUF_PIN;
  220.             new_bufp->flags &= ~BUF_PIN;
  221.             return (retval);
  222.  
  223.         }
  224.         key.data = (u_char *)op + ino[n];
  225.         key.size = off - ino[n];
  226.  
  227.         if (__call_hash(hashp, key.data, key.size) == obucket) {
  228.             /* Don't switch page */
  229.             diff = copyto - off;
  230.             if (diff) {
  231.                 copyto = ino[n + 1] + diff;
  232.                 memmove(op + copyto, op + ino[n + 1],
  233.                     off - ino[n + 1]);
  234.                 ino[ndx] = copyto + ino[n] - ino[n + 1];
  235.                 ino[ndx + 1] = copyto;
  236.             } else
  237.                 copyto = ino[n + 1];
  238.             ndx += 2;
  239.         } else {
  240.             /* Switch page */
  241.             val.data = (u_char *)op + ino[n + 1];
  242.             val.size = ino[n] - ino[n + 1];
  243.             putpair(np, &key, &val);
  244.             moved += 2;
  245.         }
  246.  
  247.         off = ino[n + 1];
  248.     }
  249.  
  250.     /* Now clean up the page */
  251.     ino[0] -= moved;
  252.     FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0] + 3);
  253.     OFFSET(ino) = copyto;
  254.  
  255. #ifdef DEBUG3
  256.     (void)fprintf(stderr, "split %d/%d\n",
  257.         ((u_short *)np)[0] / 2,
  258.         ((u_short *)op)[0] / 2);
  259. #endif
  260.     /* unpin both pages */
  261.     old_bufp->flags &= ~BUF_PIN;
  262.     new_bufp->flags &= ~BUF_PIN;
  263.     return (0);
  264. }
  265.  
  266. /*
  267.  * Called when we encounter an overflow or big key/data page during split
  268.  * handling.  This is special cased since we have to begin checking whether
  269.  * the key/data pairs fit on their respective pages and because we may need
  270.  * overflow pages for both the old and new pages.
  271.  *
  272.  * The first page might be a page with regular key/data pairs in which case
  273.  * we have a regular overflow condition and just need to go on to the next
  274.  * page or it might be a big key/data pair in which case we need to fix the
  275.  * big key/data pair.
  276.  *
  277.  * Returns:
  278.  *     0 ==> success
  279.  *    -1 ==> failure
  280.  */
  281. static int
  282. ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)
  283.     HTAB *hashp;
  284.     u_int obucket;    /* Same as __split_page. */
  285.     BUFHEAD *old_bufp, *new_bufp;
  286.     int copyto;    /* First byte on page which contains key/data values. */
  287.     int moved;    /* Number of pairs moved to new page. */
  288. {
  289.     register BUFHEAD *bufp;    /* Buffer header for ino */
  290.     register u_short *ino;    /* Page keys come off of */
  291.     register u_short *np;    /* New page */
  292.     register u_short *op;    /* Page keys go on to if they aren't moving */
  293.  
  294.     BUFHEAD *last_bfp;    /* Last buf header OVFL needing to be freed */
  295.     DBT key, val;
  296.     SPLIT_RETURN ret;
  297.     u_short n, off, ov_addr, scopyto;
  298.     char *cino;        /* Character value of ino */
  299.  
  300.     bufp = old_bufp;
  301.     ino = (u_short *)old_bufp->page;
  302.     np = (u_short *)new_bufp->page;
  303.     op = (u_short *)old_bufp->page;
  304.     last_bfp = NULL;
  305.     scopyto = (u_short)copyto;    /* ANSI */
  306.  
  307.     n = ino[0] - 1;
  308.     while (n < ino[0]) {
  309.         if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {
  310.             /*
  311.              * Ov_addr gets set before reaching this point; there's
  312.              * always an overflow page before a big key/data page.
  313.              */
  314.             if (__big_split(hashp, old_bufp,
  315.                 new_bufp, bufp, ov_addr, obucket, &ret))
  316.                 return (-1);
  317.             old_bufp = ret.oldp;
  318.             if (!old_bufp)
  319.                 return (-1);
  320.             op = (u_short *)old_bufp->page;
  321.             new_bufp = ret.newp;
  322.             if (!new_bufp)
  323.                 return (-1);
  324.             np = (u_short *)new_bufp->page;
  325.             bufp = ret.nextp;
  326.             if (!bufp)
  327.                 return (0);
  328.             cino = (char *)bufp->page;
  329.             ino = (u_short *)cino;
  330.             last_bfp = ret.nextp;
  331.         } else if (ino[n + 1] == OVFLPAGE) {
  332.             ov_addr = ino[n];
  333.             /*
  334.              * Fix up the old page -- the extra 2 are the fields
  335.              * which contained the overflow information.
  336.              */
  337.             ino[0] -= (moved + 2);
  338.             FREESPACE(ino) =
  339.                 scopyto - sizeof(u_short) * (ino[0] + 3);
  340.             OFFSET(ino) = scopyto;
  341.  
  342.             bufp = __get_buf(hashp, ov_addr, bufp, 0);
  343.             if (!bufp)
  344.                 return (-1);
  345.  
  346.             ino = (u_short *)bufp->page;
  347.             n = 1;
  348.             scopyto = hashp->BSIZE;
  349.             moved = 0;
  350.  
  351.             if (last_bfp)
  352.                 __free_ovflpage(hashp, last_bfp);
  353.             last_bfp = bufp;
  354.         }
  355.         /* Move regular sized pairs of there are any */
  356.         off = hashp->BSIZE;
  357.         for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
  358.             cino = (char *)ino;
  359.             key.data = (u_char *)cino + ino[n];
  360.             key.size = off - ino[n];
  361.             val.data = (u_char *)cino + ino[n + 1];
  362.             val.size = ino[n] - ino[n + 1];
  363.             off = ino[n + 1];
  364.  
  365.             if (__call_hash(hashp, key.data, key.size) == obucket) {
  366.                 /* Keep on old page */
  367.                 if (PAIRFITS(op, (&key), (&val)))
  368.                     putpair((char *)op, &key, &val);
  369.                 else {
  370.                     old_bufp =
  371.                         __add_ovflpage(hashp, old_bufp);
  372.                     if (!old_bufp)
  373.                         return (-1);
  374.                     op = (u_short *)old_bufp->page;
  375.                     putpair((char *)op, &key, &val);
  376.                 }
  377.                 old_bufp->flags |= BUF_MOD;
  378.             } else {
  379.                 /* Move to new page */
  380.                 if (PAIRFITS(np, (&key), (&val)))
  381.                     putpair((char *)np, &key, &val);
  382.                 else {
  383.                     new_bufp =
  384.                         __add_ovflpage(hashp, new_bufp);
  385.                     if (!new_bufp)
  386.                         return (-1);
  387.                     np = (u_short *)new_bufp->page;
  388.                     putpair((char *)np, &key, &val);
  389.                 }
  390.                 new_bufp->flags |= BUF_MOD;
  391.             }
  392.         }
  393.     }
  394.     if (last_bfp)
  395.         __free_ovflpage(hashp, last_bfp);
  396.     return (0);
  397. }
  398.  
  399. /*
  400.  * Add the given pair to the page
  401.  *
  402.  * Returns:
  403.  *    0 ==> OK
  404.  *    1 ==> failure
  405.  */
  406. extern int
  407. __addel(hashp, bufp, key, val)
  408.     HTAB *hashp;
  409.     BUFHEAD *bufp;
  410.     const DBT *key, *val;
  411. {
  412.     register u_short *bp, *sop;
  413.     int do_expand;
  414.  
  415.     bp = (u_short *)bufp->page;
  416.     do_expand = 0;
  417.     while (bp[0] && (bp[bp[0]] < REAL_KEY))
  418.         /* Exception case */
  419.         if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {
  420.             /* This is a big-keydata pair */
  421.             bufp = __add_ovflpage(hashp, bufp);
  422.             if (!bufp)
  423.                 return (-1);
  424.             bp = (u_short *)bufp->page;
  425.         } else
  426.             /* Try to squeeze key on this page */
  427.             if (FREESPACE(bp) > PAIRSIZE(key, val)) {
  428.                 squeeze_key(bp, key, val);
  429.                 return (0);
  430.             } else {
  431.                 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  432.                 if (!bufp)
  433.                     return (-1);
  434.                 bp = (u_short *)bufp->page;
  435.             }
  436.  
  437.     if (PAIRFITS(bp, key, val))
  438.         putpair(bufp->page, key, val);
  439.     else {
  440.         do_expand = 1;
  441.         bufp = __add_ovflpage(hashp, bufp);
  442.         if (!bufp)
  443.             return (-1);
  444.         sop = (u_short *)bufp->page;
  445.  
  446.         if (PAIRFITS(sop, key, val))
  447.             putpair((char *)sop, key, val);
  448.         else
  449.             if (__big_insert(hashp, bufp, key, val))
  450.                 return (-1);
  451.     }
  452.     bufp->flags |= BUF_MOD;
  453.     /*
  454.      * If the average number of keys per bucket exceeds the fill factor,
  455.      * expand the table.
  456.      */
  457.     hashp->NKEYS++;
  458.     if (do_expand ||
  459.         (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
  460.         return (__expand_table(hashp));
  461.     return (0);
  462. }
  463.  
  464. /*
  465.  *
  466.  * Returns:
  467.  *    pointer on success
  468.  *    NULL on error
  469.  */
  470. extern BUFHEAD *
  471. __add_ovflpage(hashp, bufp)
  472.     HTAB *hashp;
  473.     BUFHEAD *bufp;
  474. {
  475.     register u_short *sp;
  476.     u_short ndx, ovfl_num;
  477. #ifdef DEBUG1
  478.     int tmp1, tmp2;
  479. #endif
  480.     sp = (u_short *)bufp->page;
  481.  
  482.     /* Check if we are dynamically determining the fill factor */
  483.     if (hashp->FFACTOR == DEF_FFACTOR) {
  484.         hashp->FFACTOR = sp[0] >> 1;
  485.         if (hashp->FFACTOR < MIN_FFACTOR)
  486.             hashp->FFACTOR = MIN_FFACTOR;
  487.     }
  488.     bufp->flags |= BUF_MOD;
  489.     ovfl_num = overflow_page(hashp);
  490. #ifdef DEBUG1
  491.     tmp1 = bufp->addr;
  492.     tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
  493. #endif
  494.     if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))
  495.         return (NULL);
  496.     bufp->ovfl->flags |= BUF_MOD;
  497. #ifdef DEBUG1
  498.     (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
  499.         tmp1, tmp2, bufp->ovfl->addr);
  500. #endif
  501.     ndx = sp[0];
  502.     /*
  503.      * Since a pair is allocated on a page only if there's room to add
  504.      * an overflow page, we know that the OVFL information will fit on
  505.      * the page.
  506.      */
  507.     sp[ndx + 4] = OFFSET(sp);
  508.     sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;
  509.     sp[ndx + 1] = ovfl_num;
  510.     sp[ndx + 2] = OVFLPAGE;
  511.     sp[0] = ndx + 2;
  512. #ifdef HASH_STATISTICS
  513.     hash_overflows++;
  514. #endif
  515.     return (bufp->ovfl);
  516. }
  517.  
  518. /*
  519.  * Returns:
  520.  *     0 indicates SUCCESS
  521.  *    -1 indicates FAILURE
  522.  */
  523. extern int
  524. __get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)
  525.     HTAB *hashp;
  526.     char *p;
  527.     u_int bucket;
  528.     int is_bucket, is_disk, is_bitmap;
  529. {
  530.     register int fd, page, size;
  531.     int rsize;
  532.     u_short *bp;
  533.  
  534.     fd = hashp->fp;
  535.     size = hashp->BSIZE;
  536.  
  537.     if ((fd == -1) || !is_disk) {
  538.         PAGE_INIT(p);
  539.         return (0);
  540.     }
  541.     if (is_bucket)
  542.         page = BUCKET_TO_PAGE(bucket);
  543.     else
  544.         page = OADDR_TO_PAGE(bucket);
  545.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  546.         ((rsize = read(fd, p, size)) == -1))
  547.         return (-1);
  548.     bp = (u_short *)p;
  549.     if (!rsize)
  550.         bp[0] = 0;    /* We hit the EOF, so initialize a new page */
  551.     else
  552.         if (rsize != size) {
  553.             errno = EFTYPE;
  554.             return (-1);
  555.         }
  556.     if (!is_bitmap && !bp[0]) {
  557.         PAGE_INIT(p);
  558.     } else
  559.         if (hashp->LORDER != BYTE_ORDER) {
  560.             register int i, max;
  561.  
  562.             if (is_bitmap) {
  563.                 max = hashp->BSIZE >> 2; /* divide by 4 */
  564.                 for (i = 0; i < max; i++)
  565.                     BLSWAP(((long *)p)[i]);
  566.             } else {
  567.                 BSSWAP(bp[0]);
  568.                 max = bp[0] + 2;
  569.                 for (i = 1; i <= max; i++)
  570.                     BSSWAP(bp[i]);
  571.             }
  572.         }
  573.     return (0);
  574. }
  575.  
  576. /*
  577.  * Write page p to disk
  578.  *
  579.  * Returns:
  580.  *     0 ==> OK
  581.  *    -1 ==>failure
  582.  */
  583. extern int
  584. __put_page(hashp, p, bucket, is_bucket, is_bitmap)
  585.     HTAB *hashp;
  586.     char *p;
  587.     u_int bucket;
  588.     int is_bucket, is_bitmap;
  589. {
  590.     register int fd, page, size;
  591.     int wsize;
  592.  
  593.     size = hashp->BSIZE;
  594.     if ((hashp->fp == -1) && open_temp(hashp))
  595.         return (-1);
  596.     fd = hashp->fp;
  597.  
  598.     if (hashp->LORDER != BYTE_ORDER) {
  599.         register int i;
  600.         register int max;
  601.  
  602.         if (is_bitmap) {
  603.             max = hashp->BSIZE >> 2;    /* divide by 4 */
  604.             for (i = 0; i < max; i++)
  605.                 BLSWAP(((long *)p)[i]);
  606.         } else {
  607.             max = ((u_short *)p)[0] + 2;
  608.             for (i = 0; i <= max; i++)
  609.                 BSSWAP(((u_short *)p)[i]);
  610.         }
  611.     }
  612.     if (is_bucket)
  613.         page = BUCKET_TO_PAGE(bucket);
  614.     else
  615.         page = OADDR_TO_PAGE(bucket);
  616.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  617.         ((wsize = write(fd, p, size)) == -1))
  618.         /* Errno is set */
  619.         return (-1);
  620.     if (wsize != size) {
  621.         errno = EFTYPE;
  622.         return (-1);
  623.     }
  624.     return (0);
  625. }
  626.  
  627. #define BYTE_MASK    ((1 << INT_BYTE_SHIFT) -1)
  628. /*
  629.  * Initialize a new bitmap page.  Bitmap pages are left in memory
  630.  * once they are read in.
  631.  */
  632. extern int
  633. __init_bitmap(hashp, pnum, nbits, ndx)
  634.     HTAB *hashp;
  635.     int pnum, nbits, ndx;
  636. {
  637.     u_long *ip;
  638.     int clearbytes, clearints;
  639.  
  640.     if (!(ip = malloc(hashp->BSIZE)))
  641.         return (1);
  642.     hashp->nmaps++;
  643.     clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
  644.     clearbytes = clearints << INT_TO_BYTE;
  645.     (void)memset((char *)ip, 0, clearbytes);
  646.     (void)memset(((char *)ip) + clearbytes, 0xFF,
  647.         hashp->BSIZE - clearbytes);
  648.     ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
  649.     SETBIT(ip, 0);
  650.     hashp->BITMAPS[ndx] = (u_short)pnum;
  651.     hashp->mapp[ndx] = ip;
  652.     return (0);
  653. }
  654.  
  655. static u_long
  656. first_free(map)
  657.     u_long map;
  658. {
  659.     register u_long i, mask;
  660.  
  661.     mask = 0x1;
  662.     for (i = 0; i < BITS_PER_MAP; i++) {
  663.         if (!(mask & map))
  664.             return (i);
  665.         mask = mask << 1;
  666.     }
  667.     return (i);
  668. }
  669.  
  670. static u_short
  671. overflow_page(hashp)
  672.     HTAB *hashp;
  673. {
  674.     register u_long *freep;
  675.     register int max_free, offset, splitnum;
  676.     u_short addr;
  677.     int bit, first_page, free_bit, free_page, i, in_use_bits, j;
  678. #ifdef DEBUG2
  679.     int tmp1, tmp2;
  680. #endif
  681.     splitnum = hashp->OVFL_POINT;
  682.     max_free = hashp->SPARES[splitnum];
  683.  
  684.     free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
  685.     free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  686.  
  687.     /* Look through all the free maps to find the first free block */
  688.     first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
  689.     for ( i = first_page; i <= free_page; i++ ) {
  690.         if (!(freep = (u_long *)hashp->mapp[i]) &&
  691.             !(freep = fetch_bitmap(hashp, i)))
  692.             return (NULL);
  693.         if (i == free_page)
  694.             in_use_bits = free_bit;
  695.         else
  696.             in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
  697.         
  698.         if (i == first_page) {
  699.             bit = hashp->LAST_FREED &
  700.                 ((hashp->BSIZE << BYTE_SHIFT) - 1);
  701.             j = bit / BITS_PER_MAP;
  702.             bit = bit & ~(BITS_PER_MAP - 1);
  703.         } else {
  704.             bit = 0;
  705.             j = 0;
  706.         }
  707.         for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
  708.             if (freep[j] != ALL_SET)
  709.                 goto found;
  710.     }
  711.  
  712.     /* No Free Page Found */
  713.     hashp->LAST_FREED = hashp->SPARES[splitnum];
  714.     hashp->SPARES[splitnum]++;
  715.     offset = hashp->SPARES[splitnum] -
  716.         (splitnum ? hashp->SPARES[splitnum - 1] : 0);
  717.  
  718. #define    OVMSG    "HASH: Out of overflow pages.  Increase page size\n"
  719.     if (offset > SPLITMASK) {
  720.         if (++splitnum >= NCACHED) {
  721.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  722.             return (NULL);
  723.         }
  724.         hashp->OVFL_POINT = splitnum;
  725.         hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  726.         hashp->SPARES[splitnum-1]--;
  727.         offset = 1;
  728.     }
  729.  
  730.     /* Check if we need to allocate a new bitmap page */
  731.     if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
  732.         free_page++;
  733.         if (free_page >= NCACHED) {
  734.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  735.             return (NULL);
  736.         }
  737.         /*
  738.          * This is tricky.  The 1 indicates that you want the new page
  739.          * allocated with 1 clear bit.  Actually, you are going to
  740.          * allocate 2 pages from this map.  The first is going to be
  741.          * the map page, the second is the overflow page we were
  742.          * looking for.  The init_bitmap routine automatically, sets
  743.          * the first bit of itself to indicate that the bitmap itself
  744.          * is in use.  We would explicitly set the second bit, but
  745.          * don't have to if we tell init_bitmap not to leave it clear
  746.          * in the first place.
  747.          */
  748.         if (__init_bitmap(hashp, (int)OADDR_OF(splitnum, offset),
  749.             1, free_page))
  750.             return (NULL);
  751.         hashp->SPARES[splitnum]++;
  752. #ifdef DEBUG2
  753.         free_bit = 2;
  754. #endif
  755.         offset++;
  756.         if (offset > SPLITMASK) {
  757.             if (++splitnum >= NCACHED) {
  758.                 (void)write(STDERR_FILENO, OVMSG,
  759.                     sizeof(OVMSG) - 1);
  760.                 return (NULL);
  761.             }
  762.             hashp->OVFL_POINT = splitnum;
  763.             hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  764.             hashp->SPARES[splitnum-1]--;
  765.             offset = 0;
  766.         }
  767.     } else {
  768.         /*
  769.          * Free_bit addresses the last used bit.  Bump it to address
  770.          * the first available bit.
  771.          */
  772.         free_bit++;
  773.         SETBIT(freep, free_bit);
  774.     }
  775.  
  776.     /* Calculate address of the new overflow page */
  777.     addr = OADDR_OF(splitnum, offset);
  778. #ifdef DEBUG2
  779.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  780.         addr, free_bit, free_page);
  781. #endif
  782.     return (addr);
  783.  
  784. found:
  785.     bit = bit + first_free(freep[j]);
  786.     SETBIT(freep, bit);
  787. #ifdef DEBUG2
  788.     tmp1 = bit;
  789.     tmp2 = i;
  790. #endif
  791.     /*
  792.      * Bits are addressed starting with 0, but overflow pages are addressed
  793.      * beginning at 1. Bit is a bit addressnumber, so we need to increment
  794.      * it to convert it to a page number.
  795.      */
  796.     bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
  797.     if (bit >= hashp->LAST_FREED)
  798.         hashp->LAST_FREED = bit - 1;
  799.  
  800.     /* Calculate the split number for this page */
  801.     for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
  802.     offset = (i ? bit - hashp->SPARES[i - 1] : bit);
  803.     if (offset >= SPLITMASK)
  804.         return (NULL);    /* Out of overflow pages */
  805.     addr = OADDR_OF(i, offset);
  806. #ifdef DEBUG2
  807.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  808.         addr, tmp1, tmp2);
  809. #endif
  810.  
  811.     /* Allocate and return the overflow page */
  812.     return (addr);
  813. }
  814.  
  815. /*
  816.  * Mark this overflow page as free.
  817.  */
  818. extern void
  819. __free_ovflpage(hashp, obufp)
  820.     HTAB *hashp;
  821.     BUFHEAD *obufp;
  822. {
  823.     register u_short addr;
  824.     u_long *freep;
  825.     int bit_address, free_page, free_bit;
  826.     u_short ndx;
  827.  
  828.     addr = obufp->addr;
  829. #ifdef DEBUG1
  830.     (void)fprintf(stderr, "Freeing %d\n", addr);
  831. #endif
  832.     ndx = (((u_short)addr) >> SPLITSHIFT);
  833.     bit_address =
  834.         (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
  835.      if (bit_address < hashp->LAST_FREED)
  836.         hashp->LAST_FREED = bit_address;
  837.     free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
  838.     free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  839.  
  840.     if (!(freep = hashp->mapp[free_page]))
  841.         freep = fetch_bitmap(hashp, free_page);
  842. #ifdef DEBUG
  843.     /*
  844.      * This had better never happen.  It means we tried to read a bitmap
  845.      * that has already had overflow pages allocated off it, and we
  846.      * failed to read it from the file.
  847.      */
  848.     if (!freep)
  849.         assert(0);
  850. #endif
  851.     CLRBIT(freep, free_bit);
  852. #ifdef DEBUG2
  853.     (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
  854.         obufp->addr, free_bit, free_page);
  855. #endif
  856.     __reclaim_buf(hashp, obufp);
  857. }
  858.  
  859. /*
  860.  * Returns:
  861.  *     0 success
  862.  *    -1 failure
  863.  */
  864. #ifdef macintosh
  865. #include <Files.h>
  866. #include <Folders.h>
  867. #include <TFileSpec.h>
  868. #include <Errors.h>
  869.  
  870. typedef struct tfdsc {
  871.     struct tfdsc *    next;
  872.     FSSpec            spec;
  873. } tfdsc;
  874.  
  875. static tfdsc * tempdescs = 0;
  876.  
  877. static void closedescs()
  878. {
  879.     while (tempdescs) {
  880.         HDelete(tempdescs->spec.vRefNum, tempdescs->spec.parID, tempdescs->spec.name);
  881.         
  882.         tempdescs = tempdescs->next;
  883.     }
  884. }
  885.  
  886. /* Create a temporary file in the temp folder. 
  887. */
  888. static int
  889. open_temp(hashp)
  890.     HTAB *hashp;
  891. {
  892.     static int    id    =    0;
  893.     FSSpec        desc;
  894.     OSErr            err;
  895.     tfdsc *        nudsc;
  896.     
  897.     if (err = FindFolder(kOnSystemDisk, 'temp', true, &desc.vRefNum, &desc.parID))
  898.         return -1;
  899.     
  900.     *((long *) desc.name)        =    '\007tmp';
  901.     
  902.     do {
  903.         desc.name[4]    =    id / 1000     % 10 + '0';
  904.         desc.name[5]    =    id / 100        % 10 + '0';
  905.         desc.name[6]    =    id / 10        % 10 + '0';
  906.         desc.name[7]    =    id             % 10 + '0';
  907.         
  908.         ++id;
  909.         
  910.         err = HCreate(desc.vRefNum, desc.parID, desc.name, 'TEMP', 'TEXT');
  911.     } while (err == dupFNErr);
  912.     
  913.     hashp->fp = open(FSp2FullPath(&desc), O_RDWR);
  914.     
  915.     if (hashp->fp < 0)
  916.         return hashp->fp;
  917.     
  918.     if (!tempdescs)
  919.         atexit(closedescs);
  920.     
  921.     nudsc = malloc(sizeof(tfdsc));
  922.     
  923.     nudsc->next = tempdescs;
  924.     nudsc->spec = desc;
  925.     tempdescs     = nudsc;
  926.     
  927.     return 0;
  928. }
  929. #else
  930. static int
  931. open_temp(hashp)
  932.     HTAB *hashp;
  933. {
  934.     sigset_t set, oset;
  935.     static char namestr[] = "_hashXXXXXX";
  936.  
  937.     /* Block signals; make sure file goes away at process exit. */
  938.     (void)sigfillset(&set);
  939.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  940.     if ((hashp->fp = mkstemp(namestr)) != -1) {
  941.         (void)unlink(namestr);
  942.         (void)fcntl(hashp->fp, F_SETFD, 1);
  943.     }
  944.     (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
  945.     return (hashp->fp != -1 ? 0 : -1);
  946. }
  947. #endif
  948.  
  949. /*
  950.  * We have to know that the key will fit, but the last entry on the page is
  951.  * an overflow pair, so we need to shift things.
  952.  */
  953. static void
  954. squeeze_key(sp, key, val)
  955.     u_short *sp;
  956.     const DBT *key, *val;
  957. {
  958.     register char *p;
  959.     u_short free_space, n, off, pageno;
  960.  
  961.     p = (char *)sp;
  962.     n = sp[0];
  963.     free_space = FREESPACE(sp);
  964.     off = OFFSET(sp);
  965.  
  966.     pageno = sp[n - 1];
  967.     off -= key->size;
  968.     sp[n - 1] = off;
  969.     memmove(p + off, key->data, key->size);
  970.     off -= val->size;
  971.     sp[n] = off;
  972.     memmove(p + off, val->data, val->size);
  973.     sp[0] = n + 2;
  974.     sp[n + 1] = pageno;
  975.     sp[n + 2] = OVFLPAGE;
  976.     FREESPACE(sp) = free_space - PAIRSIZE(key, val);
  977.     OFFSET(sp) = off;
  978. }
  979.  
  980. static u_long *
  981. fetch_bitmap(hashp, ndx)
  982.     HTAB *hashp;
  983.     int ndx;
  984. {
  985.     if (ndx >= hashp->nmaps ||
  986.         !(hashp->mapp[ndx] = malloc(hashp->BSIZE)) ||
  987.         __get_page(hashp, (char *)hashp->mapp[ndx],
  988.         hashp->BITMAPS[ndx], 0, 1, 1))
  989.         return (NULL);
  990.     return (hashp->mapp[ndx]);
  991. }
  992.  
  993. #ifdef DEBUG4
  994. int
  995. print_chain(addr)
  996.     int addr;
  997. {
  998.     BUFHEAD *bufp;
  999.     short *bp, oaddr;
  1000.  
  1001.     (void)fprintf(stderr, "%d ", addr);
  1002.     bufp = __get_buf(hashp, addr, NULL, 0);
  1003.     bp = (short *)bufp->page;
  1004.     while (bp[0] && ((bp[bp[0]] == OVFLPAGE) ||
  1005.         ((bp[0] > 2) && bp[2] < REAL_KEY))) {
  1006.         oaddr = bp[bp[0] - 1];
  1007.         (void)fprintf(stderr, "%d ", (int)oaddr);
  1008.         bufp = __get_buf(hashp, (int)oaddr, bufp, 0);
  1009.         bp = (short *)bufp->page;
  1010.     }
  1011.     (void)fprintf(stderr, "\n");
  1012. }
  1013. #endif
  1014.